package leetcode;

/**
 * 平面上有 n 个点，点的位置用整数坐标表示 points[i] = [xi, yi] 。请你计算访问所有这些点需要的 最小时间（以秒为单位）。
 * <p>
 * 你需要按照下面的规则在平面上移动：
 * <p>
 * 每一秒内，你可以：
 * 沿水平方向移动一个单位长度，或者
 * 沿竖直方向移动一个单位长度，或者
 * 跨过对角线移动 sqrt(2) 个单位长度（可以看作在一秒内向水平和竖直方向各移动一个单位长度）。
 * 必须按照数组中出现的顺序来访问这些点。
 * 在访问某个点时，可以经过该点后面出现的点，但经过的那些点不算作有效访问。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-time-visiting-all-points
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author Europa
 */
public class Num1266 {

    public int minTimeToVisitAllPoints(int[][] points) {
        // 总时间
        int time = 0;
        // 长度为1就为0
        if (points.length == 1) {
            return 0;
        }
        // 计算
        for (int i = 1; i < points.length; i++) {
            // x0, y0的位置
            int x0 = points[i][0];
            int y0 = points[i][1];
            // x1, y1的位置
            int x1 = points[i + 1][0];
            int y1 = points[i + 1][1];
            // 计算x0-x1的时间, y0-y1的位置
            int x = Math.abs(x0 - x1);
            int y = Math.abs(y0 - y1);
            // 由于斜线也算做1, 所以只要比较x和y的大小
            time += Math.max(y, x);
        }
        return time;
    }

    public static void main(String[] args) {
        Num1266 num1266 = new Num1266();
        int[][] ints = {{1, 1}, {3, 4}, {-1, 0}};
        int i = num1266.minTimeToVisitAllPoints(ints);
        System.out.println(i);
    }
}
